Lý thuyết thông tin thuật toán được thành lập bởi Ray Solomonoff,[2], người đã công bố những ý tưởng cơ bản mà lĩnh vực này dựa trên phát minh của ông về xác suất thuật toán cách khắc phục các vấn đề nghiêm trọng liên quan đến việc áp dụng các quy tắc của Bayes trong thống kê. Ông lần đầu tiên mô tả kết quả của mình tại một Hội nghị tại Caltech năm 1960,[3] và trong một báo cáo, tháng 2 năm 1960, "Báo cáo sơ bộ về một lý thuyết chung về suy luận quy nạp".[4] Lý thuyết thông tin thuật toán sau đó được phát triển độc lập bởi Andrey Kolmogorov, vào năm 1965 và Gregory Chaitin, vào khoảng năm 1966.

Có một số biến thể của thông tin thuật toán hoặc độ phức tạp Kolmogorov; một chương trình được sử dụng rộng rãi nhất dựa trên các chương trình tự phân định và chủ yếu là do Leonid Levin (1974). Per Martin-Löf cũng đóng góp đáng kể vào lý thuyết thông tin về các chuỗi vô hạn. Một cách tiếp cận tiên đề đối với lý thuyết thông tin thuật toán dựa trên các tiên đề Blum (Blum 1967) đã được Mark Burgin giới thiệu trong một bài báo được trình bày để xuất bản bởi Andrey Kolmogorov (Burgin 1982). Cách tiếp cận tiên đề bao gồm các cách tiếp cận khác trong lý thuyết thông tin thuật toán. Có thể coi các biện pháp khác nhau của thông tin thuật toán là các trường hợp cụ thể của các biện pháp xác định tiên đề của thông tin thuật toán. Thay vì chứng minh các định lý tương tự, chẳng hạn như định lý bất biến cơ bản, đối với từng biện pháp cụ thể, có thể dễ dàng suy ra tất cả các kết quả như vậy từ một định lý tương ứng đã được chứng minh trong thiết lập tiên đề. Đây là một lợi thế chung của phương pháp tiên đề trong toán học. Cách tiếp cận tiên đề cho lý thuyết thông tin thuật toán đã được phát triển thêm trong cuốn sách (Burgin 2005) và áp dụng cho các số liệu phần mềm (Burgin và Debnath, 2003; Debnath và Burgin, 2003).